#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
typedef long long LL;
const int MAXN = 1e6+7;
LL arfm[MAXN];
LL arfz[MAXN];
LL rev[MAXN];
int mu[MAXN];
int prime[MAXN], p_cnt;
bool not_p[MAXN];
void Init() {
    p_cnt = 0;
    arfm[1] = 1;
    arfz[1] = 1;
    rev[1] = 1;
    mu[1] = 1;
    for (int i=2; i<MAXN; ++i) {
        if (!not_p[i]) {
            prime[p_cnt++] = i;
            arfz[i] = i;
            arfm[i] = i - 1;
            mu[i] = -1;
        }
        for (int j=0; j<p_cnt&&prime[j]*i<MAXN; ++j) {
            not_p[i*prime[j]] = true;
            if (i%prime[j] == 0) {
                arfm[i*prime[j]] = arfm[i];
                arfz[i*prime[j]] = arfz[i];
                mu[i*prime[j]] = 0;
                break;
            }
            else {
                arfz[i*prime[j]] = arfz[i] * prime[j];
                arfm[i*prime[j]] = arfm[i] * (prime[j] - 1);
                mu[i*prime[j]] = -mu[i];
            }
        }
    }
}
void solveRev(LL p) {
    rev[0] = 1;
    rev[1] = 1;
    for (int i=2; i<MAXN; ++i) {
        rev[i] = (p - rev[p%i]) * (p/i) % p;
    }
}

inline LL getArf(LL i, LL p) {
    return arfz[i] * rev[arfm[i]] % p;
}
void show(int* arr, int len) { for (int i=0; i<len; ++i) { cout<<arr[i]<<" "; } cout<<endl; }

int main() {
#ifdef hai
    freopen("in.txt", "r", stdin);
#endif
    Init();
    //show(mu, 10);
    LL n, m, p;
    int T;
    cin>>T;
    while (T--) {
        cin>>n>>m>>p;
        solveRev(p);
        LL res = 0;
        int mmin = min(n, m);
        for (int k=1; k<=mmin; ++k) {
            LL t = 0;
            for (int i=k; i<=mmin; i+=k) {
                t += mu[i/k] * (m/i) * (n/i);
            }
            t %= p;
            if (t<0) t+=p;
            res = (res + getArf(k, p) * t) % p;
        }
        printf("%lld\n", res);
    }
    return 0;
}
